The present invention generally relates to a data driven (fired) type instruction execution control method and an apparatus or a system in which the method is adopted. More particularly, the present invention is concerned with a control method for controlling the data driven (fired) type execution of instructions which method can enhance and improve the instruction executing capability or performance as well as the trace efficiency (understandability of program). The invention also concerns a connection processing system by which the above-mentioned method can be adopted.
As language developed for enhancing the productivity of software, there can be mentioned a functional language. With this functional language, the value of a function is definitely determined by the inputted values, and any one function can exert no side effects on other functions and at the same time it is insusceptible to the influences of the other functions. Thus, the functions can be executed independent of one another, making it possible to execute a plurality of processings in parallel. A machine suited for executing programs described with such functional language is generally called a data flow machine. The data drive (firing) concept or principle underlying the data flow machine resides in that execution of any operation can be carried out or fired whenever the operand data required for the operation are completely made available.
As is shown in FIG. 2 of the accompanying drawings, in the operation of the data flow machine, operands (such as data address, data, code and others) are inputted to nodes 1A to 1D represented by blocks in which names of operations (data reading, code conversion, addition and others) are inscribed, wherein each of the nodes outputs the result of the operation as executed. The inputting and outputting to and from the node are represented by arrowhead lines, respectively. The arrowhead line is referred to as the arc, while a data on the arrowhead line is referred to as the token.
Now, it is assumed, by way of example, that a token x has arrived at the left-hand input arc of the addition node 1D. In that case, since the addition can not be performed with the data or token x alone, the latter is set to the stand-by state on that input arc. Upon arrival of a token y at the right-hand input arc of the addition node 1D, the arithmetic operation (addition in this case) is immediately executed, resulting in that a token having a value of (x+y) makes appearance at the output arc of the addition node 1D.
Through similar procedure, calculations can be performed in accordance with other functional expressions such as x.sup.2 -2x+1 and others.
In the case of the data driven type instruction execution control method known heretofore such as, for example, the method disclosed in JP-A-61-123937, the data required to be rewritten for execution of instructions are contained in one and the same table together with the data which need not be rewritten, wherein the number of the input data arrived at the relevant instruction node is indicated by a rewritable counter. More specifically, in the data driven type instruction execution control system disclosed in the abovementioned publication, tables are prepared in a memory in correspondence to the individual processing program modules, respectively, wherein each table contains input/output data source table identifiers, an input data availability indicator (counter), an output data destination table identifier and an output data storing area for each associated processing program module.
Upon activation, each processing program module consults the associated table to read out the input data from the input data source table indicated by the corresponding table identifier to perform processings on the data in a sequential execution mode, the results of which are written in the predetermined output data storing area of the associated table. Subsequently, the processing program module again refers to the associated table to message the availability or readiness of the relevant input data to the input data availability indicator (counter) of the output data destination table to which the output data resulting from the above processing is to be sent. In the counter mentioned above, the number of the output data from the other program modules is placed as the initial value. An execution control program checks the value of the counter every time the input data becomes available to thereby decrement by "1" the value of that counter when it is not smaller than "2". On the other hand, when the value of the counter is "1", it is decided that all the requisite input data are completely available, whereupon the table for which the data are completely available is registered at the end of a queue. Accordingly, when there are many programs each having the counter value of "1" in the data driven type instruction execution control system described above, it is sufficient to set previously the initial values for only those tables for which the counter value is not smaller than "2". In other words, for the tables whose counters indicate "1", no initialization processing is required, whereby the amount of the initialization processings can be correspondingly reduced.
As the specific features of the data flow program, the following can be mentioned.
(1) Since the sequence in which the instructions are executed is determined on the basis of only the intra-data dependence relation (i.e. input/output relation) and because the program can be expressed in the form of a chart, improved understandability of the program can be assured.
(2) Because the parallel processing can be positively and explicitly expressed, enhancement in the processing capability can be promised by implementing the system in a multiprocessor configuration.
Concerning the queuing of the instructions to be executed according to the data flow program, a discussion is found, for example, in the "Periodical Part-II of The Institution of Electronics And Communication Engineers of Japan", 1984/6, Vol. J67-B, No. 6, pp. 645 to 661. According to the method disclosed in this literature, the system is implemented in a multiprocessor configuration, wherein the instructions are transferred among the processors in the form of packets with a first-in first-out (FIFO) queue being employed with a view to increasing the processing capability in the parallel execution of the instructions.
Further, U.S. patent application Ser. No. 753,852, now U.S. Pat. No. 4,901,274 corresponds to JP-A-61-22329 laid open on Jan. 31, 1986 and also to the above-mentioned JP-A-61-123937.
In the system disclosed in JP-A-61-123937 mentioned above, the counter values are stored in one and the same table regardless of whether the value is one or not less than two. Consequently, upon making decisions as to whether all the input data are available or not, the abovementioned table has to be consulted regardless of whether the counter value is one or not less than two, presenting thus a problem.
Further, initialization of the counters is performed at the time when the program is loaded. Accordingly, the counters have to be initialized to the initial values for all the instructions. This means that the time taken for the initialization of the counters is increased as the number of the instructions becomes greater. Besides, in the prior art system, a rewritable counter, i.e. the table in the form of RAM is employed, as mentioned previously. Consequently, there arises a problem that data can not positively be protected against the destruction upon occurrence of overrunning of the program. To overcome this problem, the data which need not be rewritten may be stored in a read-only memory (ROM) while the data required to be rewritten may be stored in a random access memory (RAM). However, simple division of the data in this way makes it difficult to associate both types of data with each other. In order to realize the linkage between the ROM and the RAM, it is necessary to store in the ROM the addresses of the data stored in the RAM. With this measure, association between both the data can certainly be established. However, in order to access a counter stored in the RAM, the ROM must once be accessed beforehand to thereby extract the address of the counter therefrom, whereupon the RAM is accessed by using the extracted address. This procedure however involves a significant increase in the amount of processing.
As will be understood from the above, the system disclosed in JP-A-61-123937 suffers from two problems to be solved, i.e. prevention of destruction of the table contents stored in the RAM and reduction in the time taken for the initialization of the counters.
On the other hand, the system disclosed in the aforementioned literature pusblished by The Institute of Electronics and Communication Engineers of Japan is the very data flow machine of multi-processor structure. Although the processing capability can be enhanced, a great amount of hardware is required. Besides, difficulty will be encountered in distincting the macroscopical parallel processings and local parallel processings from each other. In other words, the trace efficiency (i.e. understandability of program by a programmer) is degraded.
So far as only the improvement of the understandability is concerned, this can be accomplished by executing the data flow program by an inexpensive conventional on Neumann type processor with the queue being realized by software, although the possibility of processing the instructions in parallel is lost. This system can be implemented by a combination of a processor and a memory. In that case, however, the data drive concept must be emulated, as the result of which a problem arises with regard to the overhead. Further, with only the first-in first-out control of the queue, distinction between the macroscopical parallel processing and the local parallel processing is difficult to another disadvantage. Besides, executions of instructions processed in parallel must be queued. In other words, an instruction to be executed must once be registered in the queue, giving rise to a further problem.